class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.word = None

def buildTrie(words: List[str]) -> TrieNode:
    root = TrieNode()
    for s in words:
        curr = root
        for c in s:
            index = ord(c) - ord('a')
            if curr.children[index] is None:
                curr.children[index] = TrieNode()
            curr = curr.children[index]
        curr.word = s
    return root

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        rows, cols = len(board), len(board[0])
        visited = [[False] * cols for _ in range(rows)]
        res = []

        def dfs(row, col, node) -> bool:
            index = ord(board[row][col]) - ord('a')
            if not node.children[index]:
                return

            node = node.children[index]
            if node.word:
                res.append(node.word)
                node.word = None

            visited[row][col] = True
            for d in dirs:
                next_row, next_col = row + d[0], col + d[1]
                if 0 <= next_row < rows and 0 <= next_col < cols and not visited[next_row][next_col]:
                    dfs(next_row, next_col, node)
            visited[row][col] = False

        root = buildTrie(words)
        for row in range(rows):
            for col in range(cols):
                dfs(row, col, root)
        return res